package org.example.basic_sort;


/**
 * 荷兰国旗问题
 * DNF Problem
 *
 */
public class Code07_DNFProblem {
    public static void dnfProblem(int[] arr,int num) {
        int min = 0;
        int max = arr.length - 1;
        int i = 0;
        for (; i < max; ) {
            // <
            if(arr[i] < num) {
                swap(arr,min,i);
                min++;
                i++;
            } else if (arr[i] == num) {
                i++;
            }else {
                swap(arr,max,i);
                max--;
            }
        }
    }
    private static void swap(int[] arr, int j, int i) {
//        arr[i] = arr[i] ^ arr[j];
//        arr[j] = arr[i] ^ arr[j];
//        arr[i] = arr[i] ^ arr[j];
        int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = {3,5,6,3,4,5,2,6,9,0};

        dnfProblem(arr,5);
        for (int i: arr) {
            System.out.println(i);
        }
    }
}
